/*
 * Copyright 2003 Program of Computer Graphics, Cornell University
 *     580 Rhodes Hall
 *     Cornell University
 *     Ithaca NY 14853
 * Web: http://www.graphics.cornell.edu/
 * 
 * Not for commercial use. Do not redistribute without permission.
 */

#ifndef _H_KDSPLITS
#define _H_KDSPLITS

/* This file contains some classes used to evaluate potential splitting planes
 * planes for building the KD-Tree (aka axis aligned binary spatial partition tree or BSP)
 */

#include "AxisAlignedBox.h"

//split plane values
#define KDST_SPLIT_X   0
#define KDST_SPLIT_Y   1
#define KDST_SPLIT_Z   2
#define KDST_LEAF      3
#define KDST_MASK      0x03

//fp epsilon multiples used in various places
//epsilon used to expand bounding boxes before testing for geometry intersection
#define EPSM_BUILD     6.0f
//#define EPSM_BUILD     2.0f
//epsilon used when estimating effects of various split planes in AxisAlignedSplits
#define EPSM_ESTIMATE  10.0f
//#define EPSM_ESTIMATE  4.0f
//larger epsilon used when constructing bounding boxes of geometry portions within bounding boxes
#define EPSM_BIG       16.0f
//#define EPSM_BIG       10.0f

class KDSplitCode {
private:
  float splitValue;
  int splitType;
public:
  KDSplitCode() {}
  KDSplitCode(int type) { assert(type==KDST_LEAF); splitValue = 0.0f; splitType = KDST_LEAF; }
  KDSplitCode(int type, float value) {
    if (type==KDST_LEAF) { splitValue = 0.0f; splitType = KDST_LEAF; return; }
    splitValue = value;
    splitType = type&KDST_MASK;
  }
  float getSplitValue() const { return splitValue; }
  int getSplitType() const { return splitType; }
};

//maximum number of objects our all split estimator can handle
#define KDALLSPLIT_MAX 2048
class KDAEvent {
public:
  float value;
  int leftTri, rightTri;
  int leftOther, rightOther;
  void set(float _value, int lTri, int rTri, int lOther, int rOther)
  { value = _value; leftTri = lTri; rightTri = rTri; leftOther = lOther; rightOther = rOther; }
};
class ALIGN8 KDACompactEvent {
public:
  float value;
  unsigned char dLeftTri,dRightTri;
  unsigned char dLeftOther,dRightOther;
  void setTri(float _value, int dLeft, int dRight)
  { value = _value; dLeftTri = dLeft; dRightTri = dRight; dLeftOther = dRightOther = 0; }
  void setOther(float _value, int dLeft, int dRight)
  { value = _value; dLeftOther = dLeft; dRightOther = dRight; dLeftTri = dRightTri = 0; }
};
class KDAllSplitEstimator {
private:
  AxisAlignedBox bounds;
public:
  AxisAlignedBox boundsBig;   //even bigger box to use when a slightly more conservative answer is desired
private:
  F32vec4 eps;
  int totalTri, totalOther;
  int numEvents;  //number of events in each axis
  KDACompactEvent xEvents[KDALLSPLIT_MAX*2];
  KDACompactEvent yEvents[KDALLSPLIT_MAX*2];
  KDACompactEvent zEvents[KDALLSPLIT_MAX*2];
  int prepareEvents(KDACompactEvent *src, float min, float max);
public:
  KDAEvent event[KDALLSPLIT_MAX*2];
  KDAllSplitEstimator() {}
  KDAllSplitEstimator(const AxisAlignedBox &_bounds) { initialize(_bounds); }
  void initialize(const AxisAlignedBox &_bounds);
  int getTotalTri() const { return totalTri; }
  int getTotalOther() const { return totalOther; }
  void addTri(int count, const AxisAlignedBox &box);
  void addOther(int count, const AxisAlignedBox &box);
  int prepareXEvents();
  int prepareYEvents();
  int prepareZEvents();
};

//class to evaluate a fixed number of regularly-spaced axis-aligned splitting planes
//Useful for quickly estimating splitting planes when there are a large number of objects
//and we don't want to lists of all possible events and sort them

//actual number of splits is one less than this number
#define KDFIXEDSPLIT_NUM 1024
class KDFixedSplitEstimator {
private:
  AxisAlignedBox bounds;
public:
  AxisAlignedBox boundsBig;   //a bigger box to use when a slightly more conservative answer is desired
private:
  F32vec4 b; //potential split planes are bounds.min + i/b for i = 1 to 63
  F32vec4 eps;
  int totalTri, totalOther;
  int leftTriX[KDFIXEDSPLIT_NUM+1], rightTriX[KDFIXEDSPLIT_NUM+1];
  int leftTriY[KDFIXEDSPLIT_NUM+1], rightTriY[KDFIXEDSPLIT_NUM+1];
  int leftTriZ[KDFIXEDSPLIT_NUM+1], rightTriZ[KDFIXEDSPLIT_NUM+1];
  int leftOtherX[KDFIXEDSPLIT_NUM+1], rightOtherX[KDFIXEDSPLIT_NUM+1];
  int leftOtherY[KDFIXEDSPLIT_NUM+1], rightOtherY[KDFIXEDSPLIT_NUM+1];
  int leftOtherZ[KDFIXEDSPLIT_NUM+1], rightOtherZ[KDFIXEDSPLIT_NUM+1];
  float leftEventX[KDFIXEDSPLIT_NUM+1], leftEventY[KDFIXEDSPLIT_NUM+1], leftEventZ[KDFIXEDSPLIT_NUM+1];
  float rightEventX[KDFIXEDSPLIT_NUM+1], rightEventY[KDFIXEDSPLIT_NUM+1], rightEventZ[KDFIXEDSPLIT_NUM+1];
public:
  KDFixedSplitEstimator() {}
  KDFixedSplitEstimator(const AxisAlignedBox &_bounds) { initialize(_bounds); }
  void initialize(const AxisAlignedBox &_bounds);
  int getTotalTri() const { return totalTri; }
  int getTotalOther() const { return totalOther; }
  int getLeftTriCountX(int index) const { return leftTriX[index]; }
  int getLeftTriCountY(int index) const { return leftTriY[index]; }
  int getLeftTriCountZ(int index) const { return leftTriZ[index]; }
  int getRightTriCountX(int index) const { return rightTriX[index]; }
  int getRightTriCountY(int index) const { return rightTriY[index]; }
  int getRightTriCountZ(int index) const { return rightTriZ[index]; }
  int getLeftOtherCountX(int index) const { return leftOtherX[index]; }
  int getLeftOtherCountY(int index) const { return leftOtherY[index]; }
  int getLeftOtherCountZ(int index) const { return leftOtherZ[index]; }
  int getRightOtherCountX(int index) const { return rightOtherX[index]; }
  int getRightOtherCountY(int index) const { return rightOtherY[index]; }
  int getRightOtherCountZ(int index) const { return rightOtherZ[index]; }
  int getLeftTriCount(int type, int index) const {
    switch (type) {
    case KDST_SPLIT_X: return leftTriX[index];
    case KDST_SPLIT_Y: return leftTriY[index];
    case KDST_SPLIT_Z: return leftTriZ[index];
    default: return 0;
    }
  }
  int getRightTriCount(int type, int index) const {
    switch (type) {
    case KDST_SPLIT_X: return rightTriX[index];
    case KDST_SPLIT_Y: return rightTriY[index];
    case KDST_SPLIT_Z: return rightTriZ[index];
    default: return 0;
    }
  }
  int getLeftOtherCount(int type, int index) const {
    switch (type) {
    case KDST_SPLIT_X: return leftOtherX[index];
    case KDST_SPLIT_Y: return leftOtherY[index];
    case KDST_SPLIT_Z: return leftOtherZ[index];
    default: return 0;
    }
  }
  int getRightOtherCount(int type, int index) const {
    switch (type) {
    case KDST_SPLIT_X: return rightOtherX[index];
    case KDST_SPLIT_Y: return rightOtherY[index];
    case KDST_SPLIT_Z: return rightOtherZ[index];
    default: return 0;
    }
  }
  void addTri(int count, const AxisAlignedBox &box);
  void addOther(int count, const AxisAlignedBox &box);
  //integrate the counts, summing from below for left counts and from above for right counts
  void integrateCounts();
  float getLeftEventX(int index) const { return leftEventX[index]; }
  float getLeftEventY(int index) const { return leftEventY[index]; }
  float getLeftEventZ(int index) const { return leftEventZ[index]; }
  float getRightEventX(int index) const { return rightEventX[index]; }
  float getRightEventY(int index) const { return rightEventY[index]; }
  float getRightEventZ(int index) const { return rightEventZ[index]; }
  KDSplitCode getBestSplitCode(int type, int index);
  KDSplitCode getSplitCode(int type, int index);
};

#endif


